"""
冒泡排序
左右交换，大的先排好，每趟排好一个数
当长度为n时，实际趟数最多为 n-1 趟，因为最后只有一个数，是不需要再交换的

时间复杂度O(n的平方)
"""


def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
        print(li)


"""
改进：如果说一趟下来没有发生交换的动作，则说明当前列表是有序的
"""


def bubble_sort2(li):
    for i in range(len(li) - 1):
        exchange = False
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        print(li)
        if not exchange:
            return


if __name__ == '__main__':
    li = [20, 10, 2, 199, 23, 4, 6, 9]
    li2 = [20, 10, 2, 199, 23, 4, 6, 9]
    bubble_sort(li)
    print('改进后')
    bubble_sort2(li2)
